package ch09_;

import java.util.ArrayList;
import java.util.List;

public class Paren {
	public void paren0(int n) {
		if (n <= 0) return;
		char[] seq = new char[n * 2];
		paren0(seq, n, n, 0);
	}
	
	private void paren0(char[] seq, int l, int r, int count) {
		if (count == seq.length) {
			System.out.println(seq);
		}
		
		if (l > 0) {
			seq[count] = '{';
			paren0(seq, l - 1, r, count + 1);
		}
		if (r > l) {
			seq[count] = '}';
			paren0(seq, l, r - 1, count + 1);
		}
	}
	
	public void paren1(int n) {
		List<Character> list = new ArrayList<Character>();
		paren1(list, n, n);
	}
	
	private void paren1(List<Character> list, int l, int r) {
		if (l == 0 && r == 0) {
			System.out.println(list);
		}
		List<Character> al = new ArrayList<Character>(list);
		if (l > 0) {
			list.add('{');
			paren1(list, l - 1, r);
		}
		if (r > l) {
			al.add('}');
			paren1(al, l, r - 1);
		}
	}
	
	public static void main(String[] args) {
		Paren test = new Paren();
		int n = 3;
//		test.paren0(n);
		test.paren1(n);
	}
}
